<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Euclidean projection on a halfspace</title>
<link rel="canonical" href="/Users/mcgrant/Projects/CVX/examples/cvxbook/Ch08_geometric_probs/html/eucl_proj_hlf.html">
<link rel="stylesheet" href="../../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Euclidean projection on a halfspace</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Sec. 8.1.1, Boyd &amp; Vandenberghe "Convex Optimization"</span>
<span class="comment">% Joelle Skaf - 10/04/05</span>
<span class="comment">%</span>
<span class="comment">% The projection of x0 on a halfspace C = {x | a'*x &lt;= b} is given by</span>
<span class="comment">%           minimize || x - x0 ||^2</span>
<span class="comment">%               s.t.    a'*x &lt;= b</span>
<span class="comment">% It is also given by P_C(x0) = x0 + (b - a'*x0)*a/||a||^2 if a'*x0 &gt; b</span>
<span class="comment">%                           and x0                         if a'*x0 &lt;=b</span>

<span class="comment">% Input data</span>
randn(<span class="string">'seed'</span>,0);
n  = 10;
a  = randn(n,1);
b  = randn(1);
x0 = randn(n,1);    <span class="comment">% a'*x0 &lt;=b</span>
x1 = x0 + a;        <span class="comment">% a'*x1 &gt; b</span>

<span class="comment">% Analytical solution</span>
fprintf(1,<span class="string">'Computing the analytical solution for the case where a^T*x0 &lt;=b...'</span>);
pc_x0 = x0;
fprintf(1,<span class="string">'Done! \n'</span>);
fprintf(1,<span class="string">'Computing the analytical solution for the case where a^T*x0 &gt; b...'</span>);
pc_x1 = x1 + (b - a'*x1)*a/norm(a)^2;
fprintf(1,<span class="string">'Done! \n'</span>);

<span class="comment">% Solution via QP</span>
fprintf(1,<span class="string">'Computing the solution of the QP for the case where a^T*x0 &lt;=b...'</span>);
cvx_begin <span class="string">quiet</span>
    variable <span class="string">xs0(n)</span>
    minimize ( square_pos(norm(xs0 - x0)) )
    a'*xs0 &lt;= b;
cvx_end
fprintf(1,<span class="string">'Done! \n'</span>);

fprintf(1,<span class="string">'Computing the solution of the QP for the case where a^T*x0 &gt; b...'</span>);
cvx_begin <span class="string">quiet</span>
    variable <span class="string">xs1(n)</span>
    minimize ( square_pos(norm(xs1 - x1)) )
    a'*xs1 &lt;= b;
cvx_end
fprintf(1,<span class="string">'Done! \n'</span>);

<span class="comment">% Verification</span>
disp(<span class="string">'-----------------------------------------------------------------'</span>);
disp(<span class="string">'Verifying that p_C(x0) and x0_star are equal in the case where a^T*x0 &lt;=b'</span>);
disp([<span class="string">'||p_C(x0) - x0_star|| = '</span> num2str(norm(xs0 - pc_x0))]);
disp(<span class="string">'Hence they are equal to working precision'</span>);
disp(<span class="string">'Verifying that p_C(x1) and x1_star are equal in the case where a^T*x1 &gt; b'</span>);
disp([<span class="string">'||p_C(x1) - x1_star|| = '</span> num2str(norm(xs1 - pc_x1))]);
disp(<span class="string">'Hence they are equal to working precision'</span>);
</pre>
<a id="output"></a>
<pre class="codeoutput">
Computing the analytical solution for the case where a^T*x0 &lt;=b...Done! 
Computing the analytical solution for the case where a^T*x0 &gt; b...Done! 
Computing the solution of the QP for the case where a^T*x0 &lt;=b...Done! 
Computing the solution of the QP for the case where a^T*x0 &gt; b...Done! 
-----------------------------------------------------------------
Verifying that p_C(x0) and x0_star are equal in the case where a^T*x0 &lt;=b
||p_C(x0) - x0_star|| = 5.5501e-09
Hence they are equal to working precision
Verifying that p_C(x1) and x1_star are equal in the case where a^T*x1 &gt; b
||p_C(x1) - x1_star|| = 4.4303e-09
Hence they are equal to working precision
</pre>
</div>
</body>
</html>